home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 12022 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: waichung.demon.co.uk!kyn
  2. From: Kyn Wai Chung <kyn@waichung.demon.co.uk>
  3. Newsgroups: comp.lang.c++
  4. Subject: Newbie requires help!
  5. Date: Sat, 16 Mar 1996 12:44:36 +0000
  6. Organization: a
  7. Distribution: world
  8. Message-ID: <AMeOMBA0erSxEwc0@waichung.demon.co.uk>
  9. NNTP-Posting-Host: waichung.demon.co.uk
  10. X-NNTP-Posting-Host: waichung.demon.co.uk
  11. MIME-Version: 1.0
  12. X-Newsreader: Turnpike Version 1.10 <gzdqIUQAgGCVFgCv6c5ZSzseKJ>
  13.  
  14. I require help in constructing a binary search tree in c++, as i am 
  15. relatively new to the language i am not sure how to go about
  16. implementing it. 
  17.  Do i construct a class called btree or do i use the following:-
  18.  
  19.  struct node 
  20.   {
  21.    data  d;
  22.    struct node  *left;
  23.    struct node  *right;
  24.   }
  25.      
  26. if this is correct how do build a tree from this and insert words into
  27. it?
  28. The following is how i would implement a binary search tree in pascal.
  29. Your help will be much appreciated.
  30. BTW i mostly program in pascal but i felt that i needed to learn other
  31. languages.
  32.  
  33. procedure BuildTree;
  34.   begin
  35.     Root := nil;
  36.     while not eof do
  37.       begin
  38.          read(NewKey);
  39.          searchAndInsert(NewKey, {starting at} Root)
  40.       end
  41.    end {BuildTree}
  42.  
  43.  
  44. procedure SearchAndInsert(NewKey : integer; {in} var Subtree : Pointer);
  45. begin
  46.    if Subtree = nil then
  47.       begin
  48.          new(SubTree);
  49.          with SubTree^ do
  50.             begin
  51.                Key := NewKey;
  52.                Left := nil;
  53.                Right := nil
  54.             end {with}
  55.       end {then statement}
  56.    else
  57.       begin
  58.          if NewKey < SubTree^.Key then
  59.             SearchAndInsert(NewKey; {in} SubTree^.Left)
  60.          elseif NewKey > SubTree^.Key then
  61.             SearchAndInsert(NewKey; {in} SubTree^.Right)
  62.          else
  63.             writeln(NewKey, ' is a duplicate entry.')
  64.       end
  65. end {SearchAndInsert}
  66.  
  67.  
  68. procedure PrintTree(Subtree : Pointer);
  69.    begin
  70.       if Subtree <> nil then
  71.          with Subtree do
  72.             begin
  73.                PrintTree(Left);
  74.                writeln(Key);
  75.                PrintTree(Right)
  76.             end
  77.    end {PrintTree}
  78.  
  79. -- 
  80. Kyn Wai Chung
  81.